Object-based application programs, e.g. written in Java, C++, or the like, usually operate on directed graphs. These graphs comprise root objects and regular objects which are interconnected by means of pointers. During the execution of an object-based application program the graph dynamically changes as objects and/or pointers are added, modified or removed.
Object-based execution environments often support the application developer in one of the most tedious and error-prone tasks in programming, namely memory-handling. In many systems, objects are only allocated by the application program, but never explicitly de-allocated. In these systems it is the task of a so-called garbage collector to determine which objects are no longer needed and to give the memory space occupied by those objects free for new objects. The garbage collector frees-up the respective memory and returns it to the heap of unused and hence usable memory. A garbage collector is designed to, every once in a while, clean up wasted memory. In addition, the garbage collector might be used to compact memory by eliminating the gaps created by fragmentation.
Cleaning up the garbage in memory is usually done in two steps, referred to as marking and sweeping. A known SUN Java garbage collector also uses the mark-and-sweep approach according to which every root object in the system is marked initially. Then one follows all the object references inside those objects to other objects not yet marked, and so on, recursively. Finally, when there are no more references to follow, all unmarked objects are deleted.
Current garbage collection schemes are not well suited for use in resource-constrained systems because these garbage collection schemes require more volatile memory than usually available in these kind of systems.
An integrated-circuit card, more widely known as smartcard, is one example of such a resource-constrained system. Other examples are mobile and/or hand held devices, such as cellular phones, pagers, personal digital assistants, personal area network devices, and so forth.
In the following, it will be focused mainly on ICCs and smartcards in particular. The smartcard concept began in Europe prior to 1985, and is today being used in telephone systems, toll roads, game parlors, and personal computers, just to mention some applications.
In the following, the term integrated-circuit card, short ICC, will be used, because ISO uses the term to encompass all those devices where an integrated-circuit is contained within a card-size piece of plastic, or the like. Typical ICCs comprise a microprocessor (central processing unit, CPU), a read-only memory (ROM), a volatile random-access memory (RAM), and some type of the non-volatile, programmable memory, such as an EEPROM (electrically erasable programmable read-only memory). In addition, an ICC usually comprises some kind of a bus (such as a serial bus) and I/O ports for interconnection to a card terminal.
The contents of the ROM-type of memory is fixed and can not be changed once manufactured by the semiconductor company. This is a low-cost memory that occupies minimum space on the substrate. It is a disadvantage of a ROM that it cannot be changed and that it takes several months to be produced. As opposed to this, an EEPROM is erasable by the user and can be rewritten many times. ROMs and EEPROMs are the non-volatile. In other words, when the power is removed they still retain their contents.
A RAM is a volatile memory and as soon as the power is removed the data content is lost. A RAM, on the other hand, has the advantage that it is much faster writable to and readable from than ROMs and EEPROMs. A RAM is however more expensive in terms of die size. Usually, the RAM is relatively small. A RAM is typically not used for operations involving data that has to be kept permanent and consistent. Thereofor typically the non-volatile memory is used. Unfortunately, using the non-volatile memory for any and all operations has a couple of serious drawbacks. One is the extreme performance penalty that has to be paid as every memory write access is roughly 500 to thousand times slower when using an EEPROM instead of a RAM. An even more serious problem is the limitation on the amount of guaranteed write cycles, which is only 100000 times for an EEPROM.
In a resource-constrained system the volatile memory is usually significantly limited in size, and the computing power is as well significantly limited, e.g. because a small CPU is employed. Such resource-constrained systems usually also operate at low clock cycle rates.